/*************************************************************************
*File Name: nonRecursivePreOrder.cpp
*Author: Leihang
*mail: 973331055@qq.com
*Created Time: Thu 06 Aug 2020 10:35:36 PM CST
*describe: 
************************************************************************/
#include "binaryNode.h"
#include <iostream>
#include <string>
#include <stack>
using namespace std;
//非递归中序遍历
void nonRecursiveInOrder(Node* root)
{
    stack<Node*> sta;
    while(root!=NULL||!sta.empty())
    {
        if(root!=NULL)
        {
            sta.push(root);
            root=root->left;
        }
        else
        {
            //只用更换输出位置
            root=sta.top();
            cout<<root->val<<" ";
            sta.pop();
            if(root->right!=NULL)
            {
                sta.push(root->right);
                root=root->right->left;
            }
            else
                root=NULL;
        }
    }
}
int main()
{
    
    int arr[] = {4,1,3,2,5};
    Node* root = NULL;
    for(int i=0;i<5;i++)
    {
        root = build(root,arr[i]);
    }
    nonRecursiveInOrder(root);
    return 0;
}

